L378 有序矩阵中第K小的元素

题目描述：

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13. Note: You may assume k is always valid, 1 ≤ k ≤ n2.

分析思路：

有序的矩阵，查找第K个小的元素，这种问题归类到已有的查找问题，和上一种小白的问题不同，这类我们可以称之为有踪迹或者可以归类的问题，类似于已有问题的扩展。就称之为基础问题吧。

这类我们需要一个对照的模型，这个题目那，就是二分查找。为什么是二分查找尼？因为和二分查找很类似，如果不是矩阵的模式，而是一个数组的样式，那么就二分查找的问题。

然后我们就去分析这道题目为什么不能直接的使用二分查找，二分查找有一个中间值和中间值的索引：

from to 和 mid = from+ （to-from）/2

对应到这个题目就是： [0][0] 和 [n][n] mid = [0+(n-0)/2][0+(n-0)/2]

再然后就是判断第K的跳转，是 from 到 mid 还是 mid 到 from，这个就和第K小的判断有关了，需要判断 mid 在数组中是第几小，然后和K进行比较。

具体的代码实现为：

public int kthSmallest(int[][] matrix,int k){
    int n = matrix.length;
    int from = matrix[0][0];int to = matrix[n-1][n-1];

    while(from < to){
        int mid = from + (to -from)/2;
        int count = 0;// 计算mid为第几小的临时变量
        int j = matrix[0].length-1;
        // 计算mid为第几小
        for(int i = 0;i < matrix.length;i++){
            while(j >0 && matrix[i][j]>mid) j--;
            count += (j+1);
        }
        if(count <k ){
             from=mid+1;    
        }else{
            to = mid;
        }

    }
    return from;
}

再然后就是优化一部分的逻辑，或者说归纳统一的逻辑，例如确定mid是第几小，可以归纳为一个方法里面。

 public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int lo = matrix[0][0], hi = matrix[n-1][n-1];
        while(lo < hi){
            int mid = lo + (hi - lo) / 2;
            int count = countLessOrEquals(mid, matrix);
            if(count < k)
                lo = mid+1;
            else
                hi = mid;
        }
        return lo;
    }
    
    public int countLessOrEquals(int target, int[][] matrix){
        int i = matrix.length-1, j = 0;
        int count = 0;
        while(i >= 0 && j < matrix[0].length){
            if(target < matrix[i][j]){
                i--;
            }else{
                count += i+1;
                j++;
            }
        }
        return count;
    }

Published on Aug 28, 2019 in categories